package _63_数据流中的中位数;

import java.util.Comparator;
import java.util.PriorityQueue;

/*
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
 */
public class Solution {
    PriorityQueue<Integer> min = new PriorityQueue<>();
    PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
        if (max.size() == 0) {
            max.add(num);
        } else {
            if (max.size() == min.size()) {
                if (num > max.peek()) {
                    min.add(num);
                } else {
                    max.add(num);
                }
            } else if (max.size() > min.size()) {
                if (num >= max.peek()) {
                    min.add(num);
                } else {
                    Integer t = max.poll();
                    min.add(t);
                    max.add(num);
                }
            } else {
                if (num <= min.peek()) {
                    max.add(num);
                }else{
                    Integer t = min.poll();
                    max.add(t);
                    min.add(num);
                }
            }
        }
    }

    public Double GetMedian() {
        double median = 0;
        if (min.size() == max.size()) {
            median = ((double) min.peek() + (double) max.peek()) / 2;
        } else if (min.size() > max.size()) {
            median = (double) min.peek();
        } else if (min.size() < max.size()) {
            median = (double) max.peek();
        }
        return median;
    }
}
